#pragma once

#include <stdlib.h>
#include <string.h>
#include <ctime>

template <typename T>
T* MergeSort(T* Array, int Length)
{
  	T* Result = new T[Length];
	mergesort(Array, Result, 0, Length);
	delete[] Result;    
	return Array;
}

template <typename T>
T* MergeSort(T* Array, int Length, bool Direct)
{
	T* Result = MergeSort(Array, Length);

	if (!Direct)
	{
		T x;
		for (int i = 0, j = Length - 1; i < Length/2; i++, j--)
		{
			x = Array[i];
			Array[i] = Array[j];
			Array[j] = x;
		}
	}

	return Result;
}

template <typename T>
void mergesort(T* arr, T* arr2, int LeftBound, int RightBound)
{
	int len = RightBound - LeftBound;
	if (len > 2)
	{
		int MidBound = LeftBound + len/2;
		
		mergesort(arr, arr2, LeftBound, MidBound);
		mergesort(arr, arr2, MidBound, RightBound);
		memcpy(arr2 + LeftBound, arr + LeftBound, len * sizeof(T));
		
		int Counter = LeftBound, Counter1 = LeftBound, Counter2 = MidBound;

		do
			if (arr2[Counter1] < arr2[Counter2])
				arr[Counter++] = arr2[Counter1++];
			else
				arr[Counter++] = arr2[Counter2++];
		while (Counter1 < MidBound && Counter2 < RightBound);

		while (Counter1 < MidBound)
			arr[Counter++] = arr2[Counter1++];
		while (Counter2 < RightBound)
			arr[Counter++] = arr2[Counter2++];
	}

	else if (arr[LeftBound] > arr[LeftBound + 1])
	{
		T x = arr[LeftBound];
		arr[LeftBound] = arr[LeftBound + 1];
		arr[LeftBound + 1] = x;
	}
}